use std::{fmt, io::BufRead};

/// Represents an abstract syntax tree (AST) for simple expressions.
///
/// For example, the expression "1 + 2 * 3" will be represented as:
/// `S::Cons('+', vec![S::Atom('1'), S::Cons('*', vec![S::Atom('2'), S::Atom('3')])])`.
enum S {
  /// An atomic element (like a number or identifier).
  Atom(char),
  /// A compound expression with an operator (head) and its arguments (rest).
  Cons(char, Vec<S>),
}

/// Custom display formatting for AST nodes.
///
/// e.g., `(+ 1 (* 2 3))`.
impl fmt::Display for S {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    match self {
      S::Atom(i) => write!(f, "{}", i),
      S::Cons(head, rest) => {
        write!(f, "({}", head)?;
        for s in rest {
          write!(f, " {}", s)?
        }
        write!(f, ")")
      }
    }
  }
}

/// The different kinds of tokens that can be produced by the lexer.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Token {
  /// An atomic token (a digit or a letter).
  Atom(char),
  /// An operator token (like '+', '-', '*', '/', etc.).
  Op(char),
  /// Represents the end of the input.
  Eof,
}

/// The lexer converts a string input into a vector of tokens.
struct Lexer {
  tokens: Vec<Token>,
}

impl Lexer {
  /// Creates a new lexer from an input string.
  fn new(input: &str) -> Lexer {
    let mut tokens = input
      .chars()
      .filter(|it| !it.is_ascii_whitespace())
      .map(|c| match c {
        // Letters and digits are atoms.
        '0'..='9' | 'a'..='z' | 'A'..='Z' => Token::Atom(c),
        // All other characters are considered operators.
        _ => Token::Op(c),
      })
      .collect::<Vec<_>>();
    // Turn the vector into a stack where the token at the front of the
    // original input ends up at the end of the vector, ensuring that tokens
    // are processed in the correct left-to-right order.
    tokens.reverse();
    Lexer { tokens }
  }

  /// Consumes and returns the next token from the lexer.
  fn next(&mut self) -> Token {
    self.tokens.pop().unwrap_or(Token::Eof)
  }

  /// Peeks at the next token without consuming it.
  fn peek(&mut self) -> Token {
    self.tokens.last().copied().unwrap_or(Token::Eof)
  }
}

/// Top-level entry point for parsing an expression from a string.
fn expr(input: &str) -> S {
  let mut lexer = Lexer::new(input);

  // println!("\n{}", input);

  let re = expr_bp(&mut lexer, 0);

  println!();

  re
}

/// The Pratt parser function.
///
/// This function parses expressions with a binding power (precedence) higher than `min_bp`. It
/// handles prefix, infix, and postfix operators by checking their binding powers, and recursively
/// calling itself to parse subexpressions.
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
  // Parse the left-hand side (lhs) of the expression.
  let mut lhs = match lexer.next() {
    // If it's an atom, simply return it.
    Token::Atom(it) => {
      print!("{} ", it);
      S::Atom(it)
    }
    // If we see an opening parenthesis, parse the subexpression inside.
    Token::Op('(') => {
      let lhs = expr_bp(lexer, 0);
      // Expect a closing parenthesis.
      assert_eq!(lexer.next(), Token::Op(')'));
      lhs
    }
    // If it's a prefix operator, parse its operand with the appropriate binding power.
    Token::Op(op) => {
      let ((), r_bp) = prefix_binding_power(op);
      let rhs = expr_bp(lexer, r_bp);
      print!("{} ", op);
      S::Cons(op, vec![rhs])
    }
    t => panic!("bad token: {:?}", t),
  };

  // Process infix and postfix operators in a loop.
  loop {
    // Peek at the next token.
    let op = match lexer.peek() {
      Token::Eof => break, // End of input.
      Token::Op(op) => op,
      t => panic!("bad token: {:?}", t),
    };

    // First, try handling a postfix operator.
    if let Some((l_bp, ())) = postfix_binding_power(op) {
      // If the operator's left binding power is too low, stop processing.
      if l_bp < min_bp {
        break;
      }

      // Consume the postfix operator.
      lexer.next();

      // Special handling for indexing operators like '['.
      lhs = if op == '[' {
        // Parse the expression inside the brackets.
        let rhs = expr_bp(lexer, 0);
        // Expect a closing bracket.
        assert_eq!(lexer.next(), Token::Op(']'));
        S::Cons(op, vec![lhs, rhs])
      } else {
        // For a simple postfix operator like '!', wrap the current lhs.
        S::Cons(op, vec![lhs])
      };
      continue;
    }

    // Next, try handling an infix operator.
    if let Some((l_bp, r_bp)) = infix_binding_power(op) {
      // If the operator's left binding power is too low, stop processing.
      if l_bp < min_bp {
        break;
      }
      // Consume the infix operator.
      lexer.next();

      // Special handling for the ternary operator '?' (and its matching ':').
      lhs = if op == '?' {
        // Parse the middle-hand side (mhs) expression.
        let mhs = expr_bp(lexer, 0);
        // Expect the ':' token.
        assert_eq!(lexer.next(), Token::Op(':'));
        // Use the operator's right binding power for the final subexpression.
        let rhs = expr_bp(lexer, r_bp);
        S::Cons(op, vec![lhs, mhs, rhs])
      } else {
        // Use `r_bp` as the new `min_bp` of the recursive call.
        // Think about `min_bp` as the binding power of the operator to
        // the left of the current expressions.
        let rhs = expr_bp(lexer, r_bp);
        S::Cons(op, vec![lhs, rhs])
      };
      continue;
    }

    // If no applicable operator is found, break out of the loop.
    break;
  }

  // Return the fully parsed expression.
  lhs
}

/// Returns the binding power for prefix operators.
///
/// For prefix operators, we only care about the right binding power, so we return a tuple with an
/// empty left part.
fn prefix_binding_power(op: char) -> ((), u8) {
  match op {
    '+' | '-' => ((), 9),
    _ => panic!("bad op: {:?}", op),
  }
}

/// Returns the binding power for postfix operators, if the operator is recognized.
///
/// The returned tuple uses a dummy unit value for the right part, since for postfix operators we
/// only care about the left binding power.
fn postfix_binding_power(op: char) -> Option<(u8, ())> {
  let res = match op {
    '!' => (11, ()),
    '[' => (11, ()),
    _ => return None,
  };
  Some(res)
}

/// Returns the binding powers for infix operators, if the operator is recognized.
///
/// The returned tuple consists of:
/// - Left binding power (l_bp): how tightly the operator binds to the expression on its left.
/// - Right binding power (r_bp): how tightly the operator binds to the expression on its right.
fn infix_binding_power(op: char) -> Option<(u8, u8)> {
  let res = match op {
    '=' => (2, 1),
    '?' => (4, 3),
    '+' | '-' => (5, 6),
    '*' | '/' => (7, 8),
    '.' => (14, 13),
    _ => return None,
  };
  Some(res)
}

#[test]
fn tests() {
  // Single atom.
  let s = expr("1");
  assert_eq!(s.to_string(), "1");

  // Infix expression with correct precedence.
  let s = expr("1 + 2 * 3");
  assert_eq!(s.to_string(), "(+ 1 (* 2 3))");

  // More complex infix expression.
  let s = expr("a + b * c * d + e");
  assert_eq!(s.to_string(), "(+ (+ a (* (* b c) d)) e)");

  // Right-associative infix operator.
  let s = expr("f . g . h");
  assert_eq!(s.to_string(), "(. f (. g h))");

  // Mixed infix and postfix with different binding powers.
  let s = expr("1 + 2 + f . g . h * 3 * 4");
  assert_eq!(s.to_string(), "(+ (+ 1 2) (* (* (. f (. g h)) 3) 4))");

  // Double prefix operators.
  let s = expr("--1 * 2");
  assert_eq!(s.to_string(), "(* (- (- 1)) 2)");

  // Double prefix with infix.
  let s = expr("--f . g");
  assert_eq!(s.to_string(), "(- (- (. f g)))");

  // Prefix with postfix factorial.
  let s = expr("-9!");
  assert_eq!(s.to_string(), "(- (! 9))");

  // Infix with postfix factorial.
  let s = expr("f . g !");
  assert_eq!(s.to_string(), "(! (. f g))");

  // Nested parentheses should collapse.
  let s = expr("(((0)))");
  assert_eq!(s.to_string(), "0");

  // Postfix operator for array indexing.
  let s = expr("x[0][1]");
  assert_eq!(s.to_string(), "([ ([ x 0) 1)");

  // Ternary operator expressed with '?' and ':'.
  let s = expr(
    "a ? b :
         c ? d
         : e",
  );
  assert_eq!(s.to_string(), "(? a b (? c d e))");

  // Combination of assignment, ternary, and infix.
  let s = expr("a = 0 ? b : c = d");
  assert_eq!(s.to_string(), "(= a (= (? 0 b c) d))")
}

/// Main function reads lines from standard input, parses them,
/// and prints the resulting AST.
fn main() {
  for line in std::io::stdin().lock().lines() {
    let line = line.unwrap();
    let s = expr(&line);
    println!("{}", s)
  }
}
